package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 1/13/21 9:35 AM
 *
 *  https://leetcode-cn.com/problems/redundant-connection/
 */
public class _684_冗余连接 {

    public int[] findRedundantConnection(int[][] edges) {


        int[] parents = new int[edges.length + 1];

        for (int i = 1; i <= parents.length; i++) {

            parents[i] = i;
        }

        int[] result = new int[]{};

        for (int[] edge : edges) {

            if (!union(parents,edge)) {

                result = edge;
            }
        }

        return result;
    }


    private int find(int[] parents, int v) {


        while (parents[v] != v) {

            parents[v] = parents[parents[v]];
            v = parents[v];
        }

        return v;
    }

    private boolean union(int[] parents, int[] edge) {

        int p1 = find(parents, edge[0]);
        int p2 = find(parents, edge[1]);

        if (p1 == p2) {

            return false;
        }else {

            parents[p2] = p1;
        }
        return true;
    }
}
